public class MyHashTable implements HashTable {
	
	public static final int MY_LIST_MAX = 10;
	
	private int mySize;
	private int myLoad;
	private SingleLinkedList[] myArray;
	private int myMaxSize;	
	
	public MyHashTable() {
		myLoad = 10;
		myMaxSize = 10;
		myArray = new SingleLinkedList[myLoad];
		mySize = 0;
		for (int i = 0; i < myLoad; i++) {
			myArray[i] = new MySingleLinkedList();
			myArray[i].setMaxSize(MY_LIST_MAX);
		}
	}
	
	public boolean isEmpty() {
		return mySize == 0;
	}
	
	public int size() {
		return mySize;
	}
	
	public void put(String key, String value) {
		
		if (mySize * 2 < myMaxSize) {
			int index = key.hashCode() % myLoad;
			if (index < 0) {
				index += myLoad;				
			}
			int sizeOfList = myArray[index].size();
			boolean exists = false;
			
			for (int i = 0; i < sizeOfList; i += 2) {
				if (myArray[index].get(i).equals(key)) {
					myArray[index].remove(i);
					myArray[index].remove(i);
					myArray[index].insert(value, i);
					myArray[index].insert(key, i);
					exists = true;
					break;
				}
			}
			if (!exists) {
				myArray[index].insertLast(key);
				myArray[index].insertLast(value);
				mySize++;
				if (myArray[index].size() >= MY_LIST_MAX) {
					reHash();					
				}
			}
		} else {
			reHash();
			put(key, value);
		}
	}
	
	private void reHash() {
		myLoad = myLoad * 3;
		myMaxSize = myLoad * 3;
		SingleLinkedList[] newArray = new SingleLinkedList[myLoad];
		
		for(int i = 0; i < myLoad; i++) {
			newArray[i]	= new MySingleLinkedList();		
			newArray[i].setMaxSize(MY_LIST_MAX);
		}
		
		for (SingleLinkedList element : myArray) {			
			for (int i = 0; i < element.size(); i += 2) {
				String key = element.get(i);
				String value = element.get(i + 1);
				int index = key.hashCode() % myLoad;
				if (index < 0) {
					index += myLoad;					
				}
				newArray[index].insertLast(key);
				newArray[index].insertLast(value);
			}
		}
		myArray = newArray;
	}
	
	public String get(String key) {
		int index = key.hashCode() % myLoad;
		int sizeOfList = myArray[index].size();
		
		for (int i = 0; i < sizeOfList; i += 2) {
			if (myArray[index].get(i).equals(key)) {
				return myArray[index].get(i + 1);
			}
		}
		return null;	
	}
	
	public String remove(String key) {
		int index = key.hashCode() % myLoad;
		String toReturn = null;
		int sizeOfList = myArray[index].size();	
		
		for (int i = 0; i < sizeOfList; i += 2) {
			if (myArray[index].get(i).equals(key)) {
				myArray[index].remove(i);
				toReturn = myArray[index].get(i);
				myArray[index].remove(i);
				mySize--;
				break;
			}
		}
		return toReturn;	
	}
	
	public void clear() {
		for (SingleLinkedList list : myArray) {
			list.clear();		
		}
		mySize = 0;	
	}
	
	public String toString() {
		StringBuffer buffer = new StringBuffer();
		
		for (SingleLinkedList element : myArray) {			
			for (int i = 0; i < element.size(); i += 2) {
				String key1 = element.get(i);
				String value1 = element.get(i + 1);
				buffer.append(key1 + "   " + value1 + "    ");
			}
		}
		return buffer.toString();
		
	}
}